package leetcode_101_120;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class flatten_114 {
    /**
     * 给你二叉树的根结点 root ，将它展开为一个单链表
     * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
     * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
     */
    public void flatten(TreeNode root) {
        /**
         * 要求在原地更改，想法是重新构造一个二叉树，最后将root替换掉
         */
        function(root);
        //不直接 root= treeLink.right  是因为leetcode的原地修改对象地址似乎不能变
        root.left= treeLink.right.left;
        root.right= treeLink.right.right;
    }

    TreeNode treeLink = new TreeNode();
    TreeNode tl = treeLink;        //方便处理

    public void function(TreeNode root) {
        if(root==null)
            return;
        tl.right=new TreeNode(root.val);
        tl=tl.right;

        function(root.left);

        function(root.right);
    }
}